package com.leetcode.q35;

/**
 * <p> description: 搜索排序数组中目标值位置或应插入位置
 *
 * 要求时间复杂度O(log n)
 * </p>
 *
 * @author tanzc
 * @date 2022/4/1
 **/
public class SearchInsert {
    public int searchInsert(int[] nums, int target) {
        return searchInsert(nums, 0, nums.length - 1, target);
    }

    public int searchInsert(int[] nums, int l, int r, int target) {
        if (l == r) {
            if (nums[l] == target) {
                return l;
            } else if (nums[l] < target){
                return l + 1;
            } else {
                return l;
            }
        }

        int mid = (l + r) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] > target) {
            return searchInsert(nums, l, mid, target);
        } else {
            return searchInsert(nums, mid + 1, r, target);
        }
    }

    public static void main(String[] args) {
        SearchInsert searchInsert = new SearchInsert();
        int[] nums = new int[]{1};
        System.out.println(searchInsert.searchInsert(nums, 0));
    }
}
